package leetcode2;
import java.util.*;
public class Day12 {



    public List<String> topKFrequent(String[] words, int k) {
        //1.放入map中，统计每个单词出现的频率
        Map<String,Integer> map = new HashMap<>();
        for (String s:words) {
            if(map.get(s) == null) {
                map.put(s,1);
            }else {
                int val = map.get(s);
                map.put(s,val+1);
            }
        }
        //2.创建小根堆，找出出现频率前k个最高的
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o2.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        //遍历map，创建top-k
        for (Map.Entry<String,Integer> entry : map.entrySet()) {
            if(minHeap.size() < k) {
                //前面k个元素直接存入，无需与顶部元素比较
                minHeap.offer(entry);
            }else {
                Map.Entry<String,Integer> top = minHeap.peek();
                //与顶部元素比较
                if(top.getValue().compareTo(entry.getValue()) < 0) {
                    minHeap.poll();
                    minHeap.offer(entry);
                }else {//出现频率相同，比较字母顺序
                    if(top.getValue().compareTo(entry.getValue()) == 0) {
                        if(top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }

                }
            }
        }
        //3.存入List中
        List<String> list = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> top = minHeap.poll();
            list.add(top.getKey());
        }
        Collections.reverse(list);//反转
        return list;
    }




    //坏键盘打字
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String s1 = in.nextLine().toUpperCase();
            String s2 = in.nextLine().toUpperCase();
            Set<Character> set1 = new HashSet<>();
            Set<Character> set2 = new HashSet<>();
            for(int i=0;i<s2.length();i++) {
                set2.add(s2.charAt(i));
            }
            for(int i=0;i<s1.length();i++) {
                char ch = s1.charAt(i);
                if(!set2.contains(ch) && !set1.contains((ch))) {
                    set1.add(ch);
                    System.out.print(ch);
                }
            }
        }
    }

    //复制带随机指针的单链表
   /* public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        //1.第一次遍历原始数组
        while(cur != null) {
            //1.给新结点赋值
            Node tmp = new Node(cur.val);
            //2.存储对应关系
            map.put(cur,tmp);
            cur = cur.next;
        }
        //2.再次遍历
        cur = head;
        while(cur != null) {
            map.get(cur).next = map.get(cur.next); //给新结点的Next赋值
            map.get(cur).random = map.get(cur.random); //给新结点的random赋值
            cur = cur.next;
        }
        return map.get(head);
    }
*/
}
